package com.leetcode.ask;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Number239 {

    public static void main(String[] args) {
        int t[] = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        for (int i = 0; i < t.length; i++) {
            System.out.println(t[i]);
        }
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (queue.isEmpty()) {
                queue.addFirst(i);
            } else {
                if (i - queue.getFirst() >= k) {
                    queue.removeFirst();
                }
                while (!queue.isEmpty() && nums[queue.getLast()] < nums[i]) {
                    queue.removeLast();
                }
                queue.addLast(i);
            }
            if (i >= k - 1) {
                list.add(nums[queue.getFirst()]);
            }
        }
        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}
